The Viterbi algorithm is one of the most used dynamic programming algorithms for protein comparison and identification, based\r\non hidden markov Models (HMMs). Most of the works in the literature focus on the implementation of hardware accelerators\r\nthat act as a prefilter stage in the comparison process. This stage discards poorly aligned sequences with a low similarity score and\r\nforwards sequences with good similarity scores to software, where they are reprocessed to generate the sequence alignment. In\r\norder to reduce the software reprocessing time, this work proposes a hardware accelerator for the Viterbi algorithm which includes\r\nthe concept of divergence, in which the region of interest of the dynamic programming matrices is delimited. We obtained gains\r\nof up to 182x when compared to unaccelerated software. The performance measurement methodology adopted in this work takes\r\ninto account not only the acceleration achieved by the hardware but also the reprocessing software stage required to generate the\r\nalignment.
Loading....